Graphe pondéré

Ce sujet est abordé en SNT avec le thème « Localisation, cartographie et mobilité », dont l’une des capacités attendues est de savoir représenter un calcul d’itinéraire comme un problème sur un graphe. C'est donc l’occasion de compléter ce qui a été vu rapidement en \(\) classe de seconde.

Pour ce type de problèmes, qu'un GPS résout tous les jours, nous devons introduire la notion de graphe pondéré.

Définition Graphe pondéré

On appelle graphe pondéré un graphe tel que à chaque arête \(a\)  est associé un poids \(p_a\) .

Dans les problèmes de « plus court chemin », on doit avoir  \(p_a >0\) pour toutes les arêtes, et  \(p_a\) peut représenter une distance en kilomètres, un temps de parcours ou le coût d’un péage.

Dans ce type de problèmes, on a aussi besoin d’un graphe connexe, ou au moins que les deux sommets à relier soient sur la même composante connexe du graphe, pour qu’il existe un chemin qui les relie !

On peut par ailleurs simplifier le problème posé en « supprimant » tous les sommets qui sont de degré \(2\) s’ils ne sont pas l’origine ou la destination de chemin recherché. Dans ce cas, on additionne les poids des arêtes correspondantes.

On peut aussi supprimer les sommets en « impasses » s’ils ne sont pas l’origine ou la destination de chemin recherché.